package 极客算法训练营.chapter08;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 电话号码的字母组合 {
    class Solution {
        private Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};

        public List<String> letterCombinations(String digits) {
            List<String> ans = new ArrayList<>();
            if (digits == null || digits.length() == 0) return ans;
            char[] condition = digits.toCharArray();
            dfs(0, new StringBuilder(), ans, condition);
            return ans;
        }

        public void dfs(int depth, StringBuilder path, List<String> ans, char[] condition) {
            if (depth == condition.length) {
                ans.add(path.toString());
                return;
            }
            char c = condition[depth];
            String s = phoneMap.get(c);
            for (int i = 0; i < s.length(); i++) {
                path.append(s.charAt(i));
                dfs(depth + 1, path, ans, condition);
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}
